/*
  解法：双指针（快慢指针）法
  为什么：关键在于如何找到要删除的倒数第n个节点
		  一定要让操作指针指向要删除节点的前一个节点
		  用虚拟头结点的目的在：用来把“删头结点”的特殊情况，统一成“删某个结点的前驱的 next”这一普通操作，
							    这样双指针写法就不需要分支判断，代码更整洁、少错
  时间复杂度：O(n)，空间复杂度：O(1)
 */

#include <iostream>
#include <vector>

using namespace std;

// 单链表结构定义
struct ListNode
{
	int val;
	ListNode* next;
	
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
	ListNode* removeNthFromEnd(ListNode* head, int n)
	{
		ListNode* dummy = new ListNode(-1);
		dummy->next = head;
		
		ListNode* fast = dummy;
		ListNode* slow = dummy;
		
		// fast 先走 n+1 步，是为了当 fast 走到末尾时，slow 正好停在要删除节点的前一个节点
		for (int i = 0; i <= n; ++i)
		{
			fast = fast->next;
		}
		
		// fast 和 slow 一起移动
		while (fast != nullptr)
		{
			fast = fast->next;
			slow = slow->next;
		}
		
		// 删除 slow->next
		ListNode* toDelete = slow->next;
		slow->next = toDelete->next;
		delete toDelete;
		
		ListNode* newHead = dummy->next;
		delete dummy;
		return newHead;
	}
};

// 构建链表
ListNode* buildList(const vector<int>& nums)
{
	ListNode* dummy = new ListNode(-1);
	ListNode* tail = dummy;
	
	for (size_t i = 0; i < nums.size(); ++i)
	{
		tail->next = new ListNode(nums[i]);
		tail = tail->next;
	}
	
	ListNode* head = dummy->next;
	delete dummy;
	return head;
}

// 打印链表
void printList(ListNode* head)
{
	while (head != nullptr)
	{
		cout << head->val;
		if (head->next != nullptr)
		{
			cout << " -> ";
		}
		head = head->next;
	}
	cout << endl;
}

// 删除链表
void deleteList(ListNode* head)
{
	while (head != nullptr)
	{
		ListNode* temp = head;
		head = head->next;
		delete temp;
	}
}

int main()
{
	vector<int> nums = {1, 2, 3, 4, 5};
	int n = 2;
	
	ListNode* head = buildList(nums);
	
	cout << "原始链表: ";
	printList(head);
	
	Solution sol;
	ListNode* newHead = sol.removeNthFromEnd(head, n);
	
	cout << "删除倒数第 " << n << " 个节点后: ";
	printList(newHead);
	
	deleteList(newHead);
	
	return 0;
}


